import heapq
from collections import defaultdict


def prim(num_vertices, edges):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    mst_set = {0}
    heap = [(w, 0, v) for v, w in graph[0]]
    mst = []

    while heap:
        w, u, v = heapq.heappop(heap)
        if v in mst_set:
            continue
        mst_set.add(v)
        mst.append((u, v, w))
        for neighbor, cost in graph[v]:
            if neighbor not in mst_set:
                heapq.heappush(heap, (cost, v, neighbor))
    return mst

# 最小生成树的边: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
# 最小生成树的总权值: 19
# 示例使用
num_vertices = 4
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
mst = prim(num_vertices, edges)
print("最小生成树的边:", mst)
total_weight = sum([w for _, _, w in mst])
print("最小生成树的总权值:", total_weight)